package cn.bigfire.compiler.mytest;


import cn.bigfire.compiler.mytest.lexer01.Lexers;
import cn.bigfire.compiler.mytest.lexer01.Token;
import cn.bigfire.compiler.mytest.lexer01.TokenType;
import cn.bigfire.compiler.mytest.parse01.TokenReader;
import lombok.Data;
import lombok.SneakyThrows;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 *
 * int a = 5; 的描述如下
 * intDeclaration : Int Identifier ('=' additiveExpression)?;
 * //伪代码
 * MatchIntDeclare(){
 *   MatchToken(Int)；        //匹配Int关键字
 *   MatchIdentifier();       //匹配标识符
 *   MatchToken(equal);       //匹配等号
 *   MatchExpression();       //匹配表达式
 * }
 *
 */
public class JTestParse {

    public enum NodeType {
        Program,           //程序入口，根节点
        IntDeclaration,    //int声明语句
        Declaration,       //变量语句
        AssignmentStmt,    //赋值语句

        Primary,            //基础表达式
        Multiplicative,     //乘法表达式
        Additive,           //加法表达式

        Identifier,         //标识符
        IntLiteral          //整型字面量
    }

    /**
     * AST的节点。
     * 属性包括AST的类型、文本值、下级子节点和父节点
     */
    @Data
    public static class Node {
        Node parent = null;
        List<Node> children = new ArrayList<Node>();
        List<Node> readonlyChildren = Collections.unmodifiableList(children);
        NodeType nodeType;
        String text;

        public Node(NodeType nodeType, String text) {
            this.nodeType = nodeType;
            this.text = text;
        }
    }

    public static Node parseIntDeclare(String code){
        List<Token> tokens = Lexers.tokenize(code);
        TokenReader tokenReader = new TokenReader(tokens);
        return intDeclare(tokenReader);//声明语句的AST构建
    }

    public static Node intDeclare(TokenReader tokenReader){
        if (tokenReader.getTokens().size() < 1) {//只有一个int不能构成合法语句 最要要有2个token才开始识别
            return null;
        }
        Node root = null;
        Token one = tokenReader.read();
        Token two = tokenReader.read();
        if (one.getText().equals("int") && two.getTokenType().equals(TokenType.ID)) {
            root = new Node(NodeType.IntDeclaration, two.getText());//放第二个token就可以了，IntDeclaration就说明了前面的int

            Token three = tokenReader.read();//3是null，则语句格式:int a
            if (three != null) {//3不空，继续读
                if (three.getTokenType().equals(TokenType.SemiColon)) {//结束
                    return root;
                } else if (three.getTokenType().equals(TokenType.Assignment)) {//继续
                    //第一步，赋值号后面先只能放数字。
                    Token four = tokenReader.read();
                    if (four.getTokenType().equals(TokenType.Number)) {
                        Node child = new Node(NodeType.IntLiteral, four.getText());
                        root.getChildren().add(child);//添加
                    } else {
                        System.out.println("语法错误 at:" + four.getText());
                        return null;
                    }
                    //第二步，赋值号后面可以放表达式
//                    Node child = calcExpression(tokenReader);
//                    root.getChildren().add(child);//添加
                } else {
                    System.out.println("语法错误 at:" + three.getText());
                    return null;
                }
            }
        }
        return root;
    }

    /**
     * 打印ast树
     *
     * @param astRoot 树根
     */
    public void printAst(Node astRoot,int level) {
        if (astRoot != null) {
            StringBuilder tab = new StringBuilder();
            for (int i = 0; i < level; i++) {
                tab.append("\t");
            }
            System.out.println(tab.toString() + astRoot.getNodeType() + " " + astRoot.getText());
            for (Node child : astRoot.getChildren()) {
                printAst(child, level + 1);
            }
        }
    }
    
    /**
     * 基础的 int a = 5;声明语句的解析
     */
    @Test
    @SneakyThrows
    public void testParse001() {
        printAst(parseIntDeclare("int a"), 0);
        System.out.println("---------------------");
        printAst(parseIntDeclare("int a;"), 0);
        System.out.println("---------------------");
        printAst(parseIntDeclare("int a =;"), 0);//语法错误
        System.out.println("---------------------");
        printAst(parseIntDeclare("int a =5;"), 0);
        System.out.println("---------------------");
    }





    /**
     * 递归下降，四则运算的优先级，先乘除后加减。
     *
     *
     * 文法：
     * additiveExpression
     *     :   multiplicativeExpression
     *     |   additiveExpression Plus multiplicativeExpression
     *     ;
     *
     * multiplicativeExpression
     *     :   IntLiteral
     *     |   multiplicativeExpression Star IntLiteral
     *     ;
     *
     * 解析算术表达式：
     * 理解“递归”的含义在讲解上下文无关文法时，我提到了文法的递归调用，你也许会问，是否在算法上也需要递归的调用呢？
     * 要不怎么叫做“递归下降算法”呢？的确，我们之前的算法只算是用到了“下降”，没有涉及“递归”，现在，我们就来看看如何用递归的算法翻译递归的文法。
     * 我们先按照前面说的，把文法直观地翻译成算法。但是，我们遇到麻烦了。这个麻烦就是出现了无穷多次调用的情况。我们来看个例子。
     * 为了简单化，我们采用下面这个简化的文法，去掉了乘法的层次：
     * additiveExpression
     *     :   IntLiteral
     *     |   additiveExpression Plus IntLiteral
     *     ;
     * 在解析 “2 + 3”这样一个最简单的加法表达式的时候，我们直观地将其翻译成算法，结果出现了如下的情况：
     * 首先匹配是不是整型字面量，发现不是；
     * 然后匹配是不是加法表达式，这里是递归调用；
     * 会重复上面两步，无穷无尽。
     * “additiveExpression Plus multiplicativeExpression”这个文法规则的第一部分就递归地引用了自身，这种情况叫做左递归。
     * 通过上面的分析，我们知道左递归是递归下降算法无法处理的，这是递归下降算法最大的问题。怎么解决呢？
     * 把“additiveExpression”调换到加号后面怎么样？我们来试一试。
     * additiveExpression
     *     :   multiplicativeExpression
     *     |   multiplicativeExpression Plus additiveExpression
     *     ;
     * 现在我们貌似解决了左递归问题，但是会出现 结合性问题，就是顺序变了 1+2+3  应该先算1+2的，结果变成了先算2+3
     * @param code 传入代码
     * @return Node 树的根节点
     */
    @SneakyThrows
    public static Node parseCalcExpression(String code){
        List<Token> tokens = Lexers.tokenize(code);
        TokenReader tokenReader = new TokenReader(tokens);
        return additive(tokenReader);//声明语句的AST构建
    }

    /**
     * 1.语法解析：加法表达式
     * @return
     * @throws Exception
     */
//    private static Node additive(TokenReader tokens) throws Exception {
//        Node child1 = multiplicative(tokens);//先获取一个pri
//        if (child1 == null) {
//            return null;
//        }
//        Token token = tokens.read();//跟读一个
//        if (token != null && (token.getTokenType() == TokenType.Plus || token.getTokenType() == TokenType.Minus)) {
//            //如果跟着是+-号
//            Node child2 = additive(tokens);
//            Node node = new Node(NodeType.Additive, token.getText());
//            node.getChildren().add(child1);
//            node.getChildren().add(child2);
//            return node;
//        } else if (token != null && (token.getTokenType() == TokenType.Star || token.getTokenType() == TokenType.Slash)) {
//            //如果跟着是*/号
//            Node child2 = multiplicative(tokens);
//            Node node = new Node(NodeType.Multiplicative, token.getText());
//            node.getChildren().add(child1);
//            node.getChildren().add(child2);
//            return node;
//        } else if (token != null && token.getTokenType() == TokenType.Number) {
//            Node node = new Node(NodeType.IntLiteral, token.getText());
//            node.getChildren().add(child1);
//            node.getChildren().add(null);
//            return node;
//        }
//        return null;
//    }

    private static Node additive(TokenReader tokens) throws Exception {
        Node child1 = multiplicative(tokens);
        Node node = child1;       //如果后面没数据了就返回当前node

        Token token = tokens.peek();
        if (child1 != null && token != null) {
            if (token.getTokenType() == TokenType.Plus || token.getTokenType() == TokenType.Minus) {
                token = tokens.read();
                Node child2 = additive(tokens);
                if (child2 != null) {
                    node = new Node(NodeType.Additive, token.getText());
                    node.getChildren().add(child1);
                    node.getChildren().add(child2);
                } else {
                    throw new Exception("invalid additive expression, expecting the right part.");
                }
            }
        }
        return node;
    }

    /**
     * 2.语法解析：乘法表达式
     * @return
     * @throws Exception
     */
    private static Node multiplicative(TokenReader tokens) throws Exception {
        Node child1 = primary(tokens);
        Node node = child1;

        Token token = tokens.peek();
        if (child1 != null && token != null) {
            if (token.getTokenType() == TokenType.Star || token.getTokenType() == TokenType.Slash) {
                token = tokens.read();
                Node child2 = multiplicative(tokens);
                if (child2 != null) {
                    node = new Node(NodeType.Multiplicative, token.getText());
                    node.getChildren().add(child1);
                    node.getChildren().add(child2);

                } else {
                    throw new Exception("invalid multiplicative expression, expecting the right part.");
                }
            }
        }
        return node;
    }

    /**
     * 3.语法解析：基础表达式  数字和ID的识别
     *
     * @param tokens TokenReader
     * @return Node 基础节点
     */
    private static Node primary(TokenReader tokens) throws Exception {
        Node node = null;
        Token token = tokens.peek();
        if (token != null) {
            if (token.getTokenType() == TokenType.Number) {
                token = tokens.read();
                node = new Node(NodeType.IntLiteral, token.getText());
            } else if (token.getTokenType() == TokenType.ID) {
                token = tokens.read();
                node = new Node(NodeType.Identifier, token.getText());
            } else if (token.getTokenType() == TokenType.LeftParen) {
                tokens.read();
                node = additive(tokens);
                if (node != null) {
                    token = tokens.peek();
                    if (token != null && token.getTokenType() == TokenType.RightParen) {
                        tokens.read();
                    } else {
                        throw new Exception("expecting right parenthesis");
                    }
                } else {
                    throw new Exception("expecting an additive expression inside parenthesis");
                }
            }
        }
        return node;  //这个方法也做了AST的简化，就是不用构造一个primary节点，直接返回子节点。因为它只有一个子节点。
    }

    /**
     * 四则运算 声明语句的解析
     */
    @Test
    @SneakyThrows
    public void testParse002() {
        printAst(parseCalcExpression("1+2+3"), 0);//有结合性问题，应该先算1+2再算+3的
        System.out.println("---------------------");
        printAst(parseCalcExpression("2+3*5"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression("36+25+48*56"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression("2*(5+3);"), 0);
        System.out.println("---------------------");
    }


    /**
     * 对某个AST节点求值，并打印求值过程。
     * @return
     */
    private int calc(Node node, int level) {
        int result = 0;
        StringBuilder tab = new StringBuilder();
        for (int i = 0; i < level; i++) {
            tab.append("\t");
        }
        System.out.println(tab + "calc: " + node.getNodeType());

        if (NodeType.Program.equals(node.getNodeType())) {//程序类型节点
            List<Node> children = node.getChildren();
            for (Node child : children) {
                result = calc(child, level + 1);
            }
        } else if (NodeType.Additive.equals(node.getNodeType())) {//加减运算
            if (node.getChildren().size() == 2) {
                Node left = node.getChildren().get(0);
                Node right = node.getChildren().get(1);
                int leftVal = calc(left, level + 1);
                int rightVal = calc(right, level + 1);
                if ("+".equals(node.getText())) {
                    result =  leftVal + rightVal;
                } else {
                    result =  leftVal - rightVal;
                }
            }
        } else if (NodeType.Multiplicative.equals(node.getNodeType())) {//乘除运算
            if (node.getChildren().size() == 2) {
                Node left = node.getChildren().get(0);
                Node right = node.getChildren().get(1);
                int leftVal = calc(left, level + 1);
                int rightVal = calc(right, level + 1);
                if ("*".equals(node.getText())) {
                    result =  leftVal * rightVal;
                } else {
                    result =  leftVal / rightVal;
                }
            }
        } else if (NodeType.IntLiteral.equals(node.getNodeType())) {//数字
            result =  Integer.parseInt(node.getText());
        }
        System.out.println(tab + "Result: " + result);
        return result;
    }

    /**
     * 四则运算 声明语句的解析
     */
    @Test
    @SneakyThrows
    public void testParse003() {
        printAst(parseCalcExpression("1+2+3"), 0);//有结合性问题，应该先算1+2再算+3的
        calc(parseCalcExpression("1+2+3"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression("2+3*5"), 0);
        calc(parseCalcExpression("2+3*5"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression("36+25+48*56"), 0);
        calc(parseCalcExpression("36+25+48*56"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression("2*(5+3);"), 0);
        calc(parseCalcExpression("2*(5+3);"), 0);
        System.out.println("---------------------");
    }

    /**
     上述代码存在结合性问题，原因是因为加减文法的左递归问题改写了文法。把加减子文法放在了右侧
     上面的内容是第三节课的内容。

     下面是第四节课的内容。第三节课的文法可成如下格式。
     add -> mul | add + mul    (有左递归问题)
     mul -> pri | mul * pri
     pri -> Id | Num | (add)
     也可写为巴科斯范式(BNF) Antlr 和 Yacc 这两个工具都用这种写法。
     add ::= mul | add + mul
     mul ::= pri | mul * pri
     pri ::= Id | Num | (add)
     还有一种叫扩展巴科斯范式 (EBNF), 他可以使用正则表达式，如下, * 表示可以出现 0到多次
     add -> mul (+ mul)*
     其实这种写法跟标准的 BNF 写法是等价的，但是更简洁。为什么是等价的呢？因为一个项多次重复，就等价于通过递归来推导。
     从这里我们还可以得到一个推论：就是上下文无关文法包含了正则文法，比正则文法能做更多的事情。

     优先级
     由加法规则推导到乘法规则，这种方式保证了 AST 中的乘法节点一定会在加法节点的下层，也就保证了乘法计算优先于加法计算。
     那么把关系运算（>、=、<）放在加法的上层，逻辑运算（and、or）放在关系运算的上层。的确如此，我们试着将它写出来：
     exp -> or | or = exp
     or -> and | or || and
     and -> equal | and && equal
     equal -> rel | equal == rel | equal != rel
     rel -> add | rel > add | rel < add | rel >= add | rel <= add
     add -> mul | add + mul | add - mul
     mul -> pri | mul * pri | mul / pri
     pri -> Id | Literal | (exp)

     这里表达的优先级从低到高是：赋值运算、逻辑运算（or）、逻辑运算（and）、相等比较（equal）、大小比较（rel）、加法运算（add）、乘法运算（mul）和基础表达式（pri）。
     实际语言中还有更多不同的优先级，比如位运算等。
     而且优先级是能够改变的，比如我们通常会在语法里通过括号来改变计算的优先级。不过这怎么表达成语法规则呢？
     其实，我们在最低层，也就是优先级最高的基础表达式（pri）这里，用括号把表达式包裹起来，递归地引用表达式就可以了。
     这样的话，只要在解析表达式的时候遇到括号，那么就知道这个是最优先的。这样的话就实现了优先级的改变：
     pri -> Id | Literal | (exp)

     根据这个 AST 做计算会出现计算顺序的错误。不过如果我们将递归项写在左边，就不会出现这种结合性的错误。
     于是我们得出一个规律：对于左结合的运算符，递归项要放在左边；而右结合的运算符，递归项放在右边。
     所以你能看到，我们在写加法表达式的规则的时候，是这样写的：
     add -> mul | add + mul      (左递归问题)

     消除左递归我提到过左递归的情况，也指出递归下降算法不能处理左递归。
     这里我要补充一点，并不是所有的算法都不能处理左递归，对于另外一些算法，左递归是没有问题的，比如 LR 算法。
     消除左递归，用一个标准的方法，就能够把左递归文法改写成非左递归的文法。
     以加法表达式规则为例，原来的文法是“add -> add + mul”，现在我们改写成：
     add -> mul add'
     add' -> + mul add' | ε
     如果用 EBNF 方式表达，也就是允许用 * 号和 + 号表示重复，上面两条规则可以合并成一条：
     add -> mul (+ mul)*
     写成这样有什么好处呢？能够优化我们写算法的思路。对于 (+ mul)* 这部分，我们其实可以写成一个循环，而不是一次次的递归调用。伪代码如下：
     mul();
     while(next token is +){
        mul()
        createAddNode
     }
     */
    private static Node additive2(TokenReader tokens) throws Exception {
        Node mul1 = multiplicative(tokens);
        Node node = mul1;//node为累计节点，先把前面的放进去，后面计算到新的节点，会
        while (true) {
            Token token = tokens.read();
            if (token != null && (token.getTokenType().equals(TokenType.Plus) || token.getTokenType().equals(TokenType.Minus))) {
                Node mul2 = multiplicative(tokens);
                if (mul2 != null) {
                    node = new Node(NodeType.Additive, token.getText());
                    node.getChildren().add(mul1);//注意，新节点在顶层，保证正确的结合性
                    node.getChildren().add(mul2);
                    mul1 = node;   //注意，这里要把node再放回去
                } else {
                    break;
                }
            } else {
                break;
            }

        }
        return node;
    }

    @SneakyThrows
    public static Node parseCalcExpression2(String code){
        List<Token> tokens = Lexers.tokenize(code);
        TokenReader tokenReader = new TokenReader(tokens);
        return additive2(tokenReader);//声明语句的AST构建
    }
    @Test
    @SneakyThrows
    public void testParse004() {
        printAst(parseCalcExpression2("1+2+3"), 0);
        calc(parseCalcExpression2("1+2+3"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression2("2+3*5"), 0);
        calc(parseCalcExpression2("2+3*5"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression2("36+25+48*56"), 0);
        calc(parseCalcExpression2("36+25+48*56"), 0);
        System.out.println("---------------------");
        printAst(parseCalcExpression2("2*(5+3);"), 0);
        calc(parseCalcExpression2("2*(5+3);"), 0);
        System.out.println("---------------------");
    }

}
